数组_659切分数组.md

给你一个按 非递减顺序 排列的整数数组 nums 。

请你判断是否能在将 nums 分割成 一个或多个子序列 的同时满足下述 两个 条件：

每个子序列都是一个 连续递增序列（即，每个整数 恰好 比前一个整数大 1 ）。 所有子序列的长度 至少 为 3 。 如果可以分割 nums 并满足上述条件，则返回 true ；否则，返回 false 。

• 方法一

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isPossible = function (nums) {

  let dict1 = {}; // 存储数字 i 在所有子序列中还剩下的个数
  let dict2 = {}; // 存储以 i 结尾的子序列的数量
  for (let n of nums) {
    dict1[n] = (dict1[n] || 0) + 1; // 统计数字 n 的个数
  }
  for (let n of nums) {
    if (dict1[n] == 0) {
      continue;
    }
    if (dict2[n - 1] > 0) {
      // 如果存在以 n-1 结尾的子序列，则将 n 添加到该子序列中
      dict2[n - 1] -= 1;
      dict2[n] = (dict2[n] || 0) + 1;
      dict1[n] -= 1;
    } else if (dict1[n + 1] > 0 && dict1[n + 2] > 0) {
      // 如果不存在以 n-1 结尾的子序列，则新建一个长度为 3 的子序列
      dict1[n] -= 1;
      dict1[n + 1] -= 1;
      dict1[n + 2] -= 1;
      dict2[n + 2] = (dict2[n + 2] || 0) + 1;
    } else {
      return false; // 无法将 n 添加到已有的子序列中，返回 false
    }
  }
  return true;

};